Test di Wilson

Il test di Wilson per la primalità di un numero intero positivo n deriva direttamente dal teorema di Wilson. Il test si applica in questo modo: dato un numero intero positivo n (possibilmente dispari, se n ≠ 2, altrimenti è divisibile per 2), si calcola (n - 1)! + 1 e si verifica se tale numero sia divisibile per n oppure non lo sia. A quel punto, se (n - 1)! + 1 è divisibile per n allora n è primo, in caso contrario n non è primo.

Si nota immediatamente che questo test dà grandissimi problemi computazionali, come si nota da questi due esempi.

Esempio 1

Se si prende per n un numero piccolo, come n = 7, n - 1 = 6, si deve calcolare

$6!+1=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6+1=721=7\cdot 103$

e, quindi, divisibile per 7.

Esempio 2

Se prendo per n un numero molto grande, come n = 10⁵ + 1, è necessario fare 10⁵ operazioni, di cui 10⁵ - 1 prodotti di numeri molto grandi, il che richiede molto tempo e crescente difficoltà di calcolo.

Utilizzabilità del test

Si capisce quindi che questo test è in pratica inutilizzabile per numeri grandi, e che si basa su un algoritmo esponenziale (la quantità di calcoli è basata su (n - 1)! il cui calcolo è esponenziale). Più utili, per trattare numeri grandi, sono i test di Lucas - Lehmer e test di Miller - Rabin.

Voci correlate

• Teorema di Wilson
• Numero primo
• Pseudoprimo
• Test di Fermat
• Test di Lucas-Lehmer
• Test di Miller-Rabin